#include <stdio.h>
#include "../global.h"
#include "list.h"
#include "sort.h" //.h就报错，.c又因为.c文件有main函数所以就必须去掉！！！

/**
 * 思路：
 *     和之前的不同，用到结点再申请
 *     链表初始化
 *     链表插入结点
 *     链表删除节点
 *     链表查找（不是链表的强项）
 *     链表长度
 *     链表销毁
 *     
 *     链表排序
 *     合并
 *     判断是否有环
 *     找出环节点
 *     环的长度
 * 
 * */

static ListElemType listArr[LISTSIZE];

VOID InitList(LIST* list,ListElemType* head)
{
	if(head == NULL) return ;
	//和前面不一样，不用init
}

LIST* InsertNode(LIST* head,ListElemType data)
{
	LIST* t = NULL;
	if(head == NULL) //头结点仍然为空
	{
		head = (LIST*)MALLOC(sizeof(LIST));
		head->data = data;
		head->next = NULL;
	}
	else
	{
		t = head; //赋值头结点
		while(t->next != NULL)
		{
			t = t->next;
		}
		t->next = (LIST*)MALLOC(sizeof(LIST));
		t->next->data = data;
		t->next->next = NULL;
	}

	return head; //返回头结点
}

VOID FreeList(LIST* head)
{
	if(head == NULL) return ;
	LIST* t = head;
	while(t != NULL)
	{
		head = t->next;
		FREE(t);
		t = head;
	}

}
/**
 * 删除链表节点
 * 1-删除成功
 * 0-删除失败
 * 同时销毁该节点
 * */
INT16 DelNode(LIST* head,ListElemType data)
{
	if(head == NULL) return 0;
	LIST* t = head;
	LIST* tPre = NULL;
	while(t->next != NULL)
	{
		tPre = t->next;
		if(tPre->data == data)
		{
			t->next = tPre->next; //如果下一个结点是要删除的结点就让该节点的前一个结点指向该节点的后一个结点
			FREE(tPre); //再销毁
			return 1; //删除成功
		}
	}

	if(t->data == data)
	{
		FREE(t); //t这个结点之前的结点应该是指向NULL了吧
		return 1;
	}
	else
	{
		return 0; //没有该节点
	}

}

/**
 * 查找结点
 * 返回该节点的指针
 * */
LIST* FindNode(LIST* head,ListElemType data)
{
	LIST* t = head;
	while(t->next != NULL)
	{
		if(t->data == data)
		{
			return t;
		}
	}
	return NULL;
}

/**
 * 链表长度，返回链表长度
 * */
INT16 LenOfList(LIST* head)
{
	if(head == NULL) return 0;
	INT16 len = 0;
	LIST* t = head;
	while(t != NULL)
	{
		len++;
		t = t->next;
	}
	return len;
}




VOID PrintList(LIST* const head) //反正这个指针不能被改变
{
	if(head == NULL) return ;
	 LIST* t = head;
	while(t != NULL)
	{
		printf("%d\n", t->data);
		t = t->next;
	}
}


/*
* 反转单链表
* 三指针 pre cur next
*/
LIST* ReverseList(LIST* head)
{
	if(head == NULL) return NULL;
	LIST* pre = NULL;
	LIST* cur = head;
	LIST* next = cur->next;

	while(cur != NULL)
	{
		cur->next = pre;
		pre = cur;
		cur = next;
		next = cur->next;


	}

	return pre;
}

/*
* 判断单链表是否有环？
* 快慢指针，快/慢 = 2
* 1-yes 0-no
*/
LIST* IsLoopList(LIST* head)
{
	LIST *slow = head,*fast = head->next;
	while(slow != NULL)
	{
		if(slow == fast)
		{
			return slow;
		}
		slow = slow->next;
		fast = fast->next->next;
	}

	return NULL;
}

/*
* 判读单链表环的长度,这个应该合并到上面的判断中  不知道(VOID*)0 能不能和0比较
*/
INT16 LoopListLen(LIST* head)
{
	LIST* node = IsLoopList(head);
	if(!node) return 0;
	INT16 len = 0;
	LIST* t = node->next;
	while(t != node)
	{
		len++;
		t = t->next;
	}
	return (len+1);
}

/*
* 单链表环的入口结点
* 相遇的结点一定是在环中的，所以应该先判断这个环的长度
*/
LIST* EnterNodeOfLoopList(LIST* head)
{
	INT16 len = LoopListLen(head);
	if(!len) return NULL;
	LIST* slow = head;
	LIST* fast = head;
	while(len != 0)
	{
		fast = fast->next;
		len--;
	}

	while(slow != fast)
	{
		slow = slow->next;
		fast = fast->next;
	}
	
	return slow;
}

#ifdef LIST_DEBUG
INT16 main(INT16 argc, char const *argv[])
{
	LIST* head = NULL;
	for (INT16 i = 0; i < 10; i++)
    {
        head = InsertNode(head, i);
    }
	PrintList(head);

    FreeList(head);

	return 0;
}

#endif

/*********    单链表的相关练习题     **********/

// 链表排序
/**
 * 小->大
 * 根据链表节点值的大小排序,快排还是冒泡还是选择？冒泡好写但是时间复杂度O(n^2)
 * 最后返回头结点
 * 
 * 只交换值，不交换值对应的地址
 * */
LIST* BubbleSortList(LIST* head)
{
	if(head == NULL) return NULL;
	LIST *tPre=head,*tNext = head->next;

	while(tPre != NULL)
	{
		while(tNext != NULL)
		{
			if(tPre->data > tNext->data)
			{
				SWAP(tPre->data,tNext->data);
			}
			tNext = tNext->next;
		}
		tPre = tPre->next;
	}

	return head;
}

/**
 * 先把链表里的值拿出来进行排序，排好后在建立链表，快排平均O(nlogn)  ,建立链表O(n)
 * 
 * */
LIST* QuickSortList(LIST* head)
{
	if(head == NULL) return NULL;
	LIST* t = head;
	INT16 len = LenOfList(head);
	INT16 *nums = (INT16*)malloc(sizeof(INT16)*len);
	INT16 i =0;
	while(t != NULL)
	{
		nums[i++] = t->data;
		t = t->next;
	}

	QuickSort(nums,0,len-1);
	t = head;
	i=0;
	while(t != NULL)
	{
		t->data = nums[i++];
		t = t->next;
	}

	return head;

}


